第8.7节 CART生成与剪枝算法

各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。

本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！

• 8.7 CART生成与剪枝算法
• 8.7.1 CART算法
• 8.7.2 分类树生成算法
• 8.7.3 分类树生成示例
• 8.7.4 分类树剪枝步骤
• 8.7.5 分类树剪枝示例
• 8.7.6 小结
• 引用

8.7 CART生成与剪枝算法

在第8.4节中，笔者分别介绍了用ID3和C4.5这两种算法来生成决策树。其中ID3算法每次用信息增益最大的特征来划分数据样本，而C4.5算法每次用信息增益比最大的特征来划分数据样本。接下来，再来看另外一种采用基尼不纯度（Gini Impurity）为标准的划分方法，CART算法。

8.7.1 CART算法

分类与回归树（Classification And Regression Tree, CART），是一种既可以用于分类也可以用于回归的决策树，同时它也是应用最为广泛的决策树学习方法之一。CART假设决策树是二叉树，内部节点特征的取值均为“是”和“否”，左分支取值为“是”，右分支取值为“否”。这样，决策树在构建过程中就等价于递归地二分每个特征，将整个特征空间划分为有限个单元[1]。

在本书中，笔者暂时只对其中的分类树进行介绍。总体来讲，利用CART算法来构造一棵分类树需要完成两步： ①基于训练数据集生成决策树，并且生成的决策树要尽可能大。②用验证集对已生成的树进行剪枝并选择最优子树。

8.7.2 分类树生成算法

在介绍分类树的生成算法前，让我们先来看一看新引入的划分标准——基尼不纯度。在分类问题中，假设某数据集包含个类别，样本点属于第类的概率为，则概率分布的基尼不纯度定义为

因此，对于给定的样本集合，其基尼不纯度为

其中，是中属于第k类的样本子集，表示类别k中的样本数，是类别的个数。

从基尼不纯度的定义可以看出，若集合中存在样本数的类别越多，则其对应的“不纯度”也会越大，直观地说也就是该集合“不纯”，这也很类似于信息熵的性质。相反，若该集合中只存在一个类别，则其对应的基尼不纯度就会是0，因此，在通过CART算法构造决策树时，会选择使基尼不纯度达到最小值的特征取值进行样本划分。

为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！

同时，在决策树的生成过程中，如果样本集合根据特征是否取某一可能值被分割成和两部分，即